Diffie-Hellmani võtmevahetus

Diffie-Hellmani võtmevahetus on avaliku võtme krüptograafias kasutusel olev algoritm, mille abil saab moodustada krüptograafilisi võtmeid ja neid mitteturvaliste arvutivõrkude kaudu jagada. See oli üks esimesi avalikustatud rakenduslikke meetodeid, mille abil avalikke võtmeid vahetada sai. Varem pidid sõnumi krüpteerimiseks ning dekrüpteerimiseks nii sõnumi saatja kui vastuvõtja omama ühte ja sama võtit. See omakorda tähendas, et saatja pidi kuidagi selle võtme vastuvõtjani toimetama, mida aga on väga keeruline turvaliselt teha. Diffie-Hellmani algoritm võimaldab kahel osapoolel, kellel pole omavahel eelnevalt mingit kokkupuudet olnud, kokku leppida ühise salajase võtme. Nad saavad kasutada suhtluseks avalikku arvutivõrku, kuna osapoolte saadetud sõnumite sisu teadmisest ei piisa, et ära arvata kokku lepitud salajast võtit. Pärast salajase võtme kokku leppimist saavad osapooled kasutada seda võtit edasise suhtluse krüpteerimiseks sümmeetrilise algoritmiga.

Whitfield Diffie ja Martin Hellman avalikustasid algoritmi 1976. aastal. 1970. aastate algul tegeles Suurbritannia signaalluureasutus samuti aktiivselt krüptograafiliste võtmete jagamise probleemiga. Nende tegevust juhtis James H. Ellis, kes mõtles välja avaliku võtmevahetuse skeemi, kuid ei suutnud leida matemaatilist funktsiooni, mis rahuldaks vajalikke nõudeid. Tema alluvuses töötasid C.C. Cocks ja M.J. Williamson, kellel oli rohkem edu matemaatiliste funktsioonide tuletamisel. Cocks mõtles 1973. aastal välja algoritmi, mis on analoogiline RSA algoritmiga. Williamson avastas 1975. aastal Diffie-Hellmani algoritmi. Kumbki neist avastustest laiemat tuntust ei saavutanud, kuna tulemused olid salastatud kuni 1999. aastani.

Diffie-Hellmani protokoll oma algsel kujul ei võimalda kasutajate autentimist (st me ei saa kindlad olla, kas teine osapool on see, kelle ta väidab end olevat). Seetõttu tuleb reaalses kasutuses alati kasutada sertifitseeritud avalikke võtmeid. Kombineerides sertifikaate ning igal sessioonil uue avaliku võtme genereerimist, on võimalik saavutada perfect forward secrecy. Sellist algoritmi varianti nimetatakse efemeerseks Diffie-Hellmani võtmevahetuseks.

Diffie-Hellmani algoritmile järgnes 1976. aastal teine populaarne avaliku võtme protokoll RSA, mis võimaldab lisaks krüpteerimisele ka turvalist allkirjastamist.

Algoritmi kirjeldus

Diffie-Hellmani võtmevahetuse tulemusena teavad kaks osapoolt ühist salajast numbrit nii, et nende osapoolte infovahetust pealt kuulates ei ole kolmandal osapoolel võimalik seda numbrit tuvastada.

Graafiliselt võib algoritmi kirjeldada, kasutades mustrite liitmist. Eeldame, et kokku liidetud mustrist esialgsete mustrite tuvastamine on väga keeruline probleem.

Esmalt lepivad Alice (A) ja Bob (B) kokku ühises mustris. Seejärel valib kumbki endale salajase mustri, mida ainult tema teab, ning liidab selle ühisele mustrile. Saadud tulemused vahetatakse omavahel. Nüüd liidab kumbki osapool teise käest saadud mustrile enda salajase mustri. Tulemusena on mõlemal identne muster, mis ongi ühiseks saladuseks.

Matemaatiline kirjeldus

Algoritmis kasutatakse kahte avalikku ning eelnevalt kokku lepitud muutujat p ning g, kus p on algarv ning g on tema primitiivne juur.

1. Alice ja Bob lepivad kokku p ja g
2. Alice valib enda salajase võtme a. Seejärel arvutab ta enda avaliku võtme ja saadab selle Bobile $A=g^{a}{\pmod {p}}$
3. Bob valib enda salajase võtme b. Seejärel arvutab ta enda avaliku võtme ja saadab selle Alice'ile $B=g^{b}{\pmod {p}}$
4. Alice arvutab $K=B^{a}{\pmod {p}}$
5. Bob arvutab $K=A^{b}{\pmod {p}}$
6. Alice ja Bob teavad ühist salajast arvu K

Alice ja Bob said arvutuste tulemusena sama arvu K, kuna
$A^{b}{\pmod {p}}=(g^{a}{\pmod {p}})^{b}{\pmod {p}}=(g^{a})^{b}{\pmod {p}}=(g^{b})^{a}{\pmod {p}}=(g^{b}{\pmod {p}})^{a}{\pmod {p}}=B^{a}{\pmod {p}}$

Leitud arvu K saavad Alice ja Bob kasutada võtmena edasise suhtluse krüpteerimiseks mõne sümmeetrilise algoritmi abil. Eeldusel, et algarv p on piisavalt suur (2015. aasta seisuga võib öelda, et mõistlik piir on 1024 bitti, turvaline piir 2048 bitti ), ei ole kolmandal osapoolel võimalik mõistliku aja jooksul leida arvu K, teades ainult arve p, g, A, B.
Ülesannet, kuidas leida K, kui on teada p, g, A, B, nimetatakse Diffie-Hellmani probleemiks.

Üldistus üle tsükliliste rühmade

Diffie-Hellmani algoritmi saab laiendada üle kõikide sobivate tsükliliste rühmade, eeldusel et Diffie-Hellmani probleemi on selles rühmas raske lahendada ning rühma tehted on võimalik efektiivselt implementeerida. Algoritmi kirjeldus:

1. Alice ja Bob lepivad kokku n-järku lõpliku tsüklilise rühma G ja selle moodustaja g.
2. Alice valib juhusliku naturaalarvu a nii, et 1 ≤ a < n, ja saadab Bobile g^a.
3. Bob valib juhusliku naturaalarvu b nii, et 1 ≤ b < n, ja saadab Alice'ile g^b.
4. Alice arvutab ühise saladuse K = (g^b)^a.
5. Bob arvutab ühise saladuse K = (g^a)^b.

Rohkem kui kaks osapoolt

Diffie-Hellmani algoritmi on võimalik kasutada ühise salajase numbri kokku leppimiseks ka kolme või enama osapoole korral. Näiteks kolme osaleja (Alice, Bob ja Carol) korral (kõik tehted modulo p):

1. Kõik osalejad lepivad kokku arvudes p ja g.
2. Kõik osalejad valivad enda salajase võtme, vastavalt a, b ja c.
3. Alice'ist algav jada
   1. Alice arvutab g^a ja saadab tulemuse Bobile.
   2. Bob arvutab (g^a)^b = g^ab ja saadab tulemuse Carolile.
   3. Carol arvutab K = (g^ab)^c = g^abc, mis ongi ühiseks saladuseks.
4. Bobist algav jada
   1. Bob arvutab g^b ja saadab tulemuse Carolile.
   2. Carol arvutab (g^b)^c = g^bc ja saadab tulemuse Alice'ile.
   3. Alice arvutab K = (g^bc)^a = g^bca = g^abc.
5. Carolist algav jada
   1. Carol arvutab g^c ja saadab tulemuse Alice'ile.
   2. Alice arvutab (g^c)^a = g^ca ja saadab tulemuse Bobile.
   3. Bob arvutab K = (g^ca)^b = g^cab = g^abc.

Osalejad on jõudnud kõik ühise saladuseni K nii, et kolmandal osapoolel, kes küll teab g^a, g^b, g^c, g^ab, g^ac, g^bc, ei ole võimalik leida K = g^abc.

Üldjuhul tuleb silmas pidada kahte põhimõtet

• Iga jada algab arvuga g ning peab ühekordselt läbi käima kõik osalejad, kes astendavad saadud vahetulemust oma salajase võtmega.
• Iga jada jõuab ühise saladuseni siis, kui viimane osaleja rakendab enda salajast võtit. Oluline on, et pärast seda arvutust ei saadetaks tulemust enam edasi. Vahepealsed tulemused võivad olla kõik avalikud.

Arvutuste järjekorda optimeerides on iga osaleja teostatavate astendamiste arvu võimalik vähendada log₂(N) + 1 astendamiseni.

Kasutusvaldkonnad võrguprotokollides

Diffie-Hellmani võtmevahetust toetavad mitmed interneti protokollid. Kõige populaarsemad neist on TLS/SSL, SSH ning IPsec. Kõik protokollid kasutavad Diffie-Hellmani võtmevahetust esialgses faasis, et kokku leppida salajast võtit, mida edasipidi suhtluse krüpteerimisel kasutada.

Turvalisus

Vahendajarünne

Õigete tingimuste täitmisel on Diffie-Hellmani protokoll väga turvaline, aga kahjuks on praktilistes rakendustes esinenud mitmeid puudujääke. Need on võimaldanud mitmesuguseid rünnakuid algoritmi implementatsioonide vastu..

Vahendajarünne

Kuna Diffie-Hellmani protokoll ei võimalda teise osapoole autentimist, siis on selle vastu võimalik kasutada vahendajarünnet (ingl man-in-the-middle-attack). Alice ja Bob soovivad omavahel kokku leppida ühist saladust, aga kolmas osapool (Mallory) sekkub nendevahelisse avalike võtmete vahetusse. Mallory loob kaks sideseanssi, ühe Alice'iga ning teise Bobiga. Alice'ile ütleb ta, et on Bob, ning Bobile, et on Alice. Kuna nii Alice kui Bob usaldavad seda informatsiooni (neil pole võimalik teist osapoolt autentida), siis lepivad mõlemad Malloryga kokku saladuse, mida kasutavad oma sõnumite krüpteerimiseks. See võimaldab Malloryl dekrüpteerida Alice'i ja Bobi sõnumeid ilma, et nood seda tuvastada suudaksid. Kui Mallory enam ei vahenda Alice'i ja Bobi sõnumeid, siis saavad nad teada, et keegi kuulas nende omavahelist sidet pealt, kuna Alice ja Bobi saladused ei kattu ning nad ei saa enam üksteise sõnumeid dekrüpteerida.

Lahendamaks vahendajaründe probleemi, tuleb teise osapoole autentimiseks kasutada mingisugust meetodit. Üheks võimaluseks on STS protokoll, mis ühendab endas Diffie-Hellmani võtmevahetuse ning osapoolte autentimise.

Logjam

2015. aastal avaldatud uurimuses kirjeldatakse, kuidas sooritada rünnet TLS protokolli vastu, mis kasutab Diffie-Hellmani algoritmi. Rünne kasutab ära asjaolu, et Diffie-Hellmani probleemi lahendamise võib jagada kaheks eraldi osaks, millest üks sõltub ainult algarvust p ning mis on võimalik sooritada enne reaalset võtmevahetuse toimumist. See on osa, mis nõuab suurema enamuse vajalikust arvutusvõimsusest. Kui see eelnev arvutus (kasutatava p jaoks) on tehtud, siis võtmevahetuse ajal avalikest võtmetest salajaste arvutamine on suhteliselt vähest arvutusvõimsust nõudev.

Esimese osa arvutamine vajab siiski väga suurt ressurssi, 512-bitise p juures kulub suurel arvutikobaral selle arvutamiseks umbes nädal, 768-bitise juures mõnikümmend aastat ning 1024-bitise juures veel 1000 korda rohkem aega. Siiski on piisava arvutusvõimsuse korral ka tänapäeva superarvutitega võimalik see arvutus sooritada 1024-bitise p korral. Alates 2048-bitiste arvude korral pole see arvutus enam reaalne.

Olulise turvaprobleemi tekitab see, et väga paljud serverid kasutavad samu algarve kõikide seansside jaoks. Seega mõne p jaoks arvutuste sooritamine annab ligipääsu suurele osale seni turvaliseks arvatud infovahetusele. Lisaks võimendab probleemi see, et paljud serverid toetavad iganenud standardit export DHE, mis kasutab 512-bitist algarvu. Kuigi see ei ole enamasti vaikimisi pakutud standard, on pahatahtlikul ründajal tihtipeale siiski võimalik mõjutada serveri ja kasutaja vahelist kokkulepet nii, et nad hakkavad kasutama seda nõrka standardit. Kui ründaja lisaks teab algaarvu p, siis on tal juba üpris lihtne ära arvata kasutatavad salajased võtmed ning edasine suhtlus dekrüpteerida.

Välislingid

• Public Key Cryptography: Diffie-Hellman Key Exchange Video, mis selgitab Diffie-Hellman algoritmi
• Is there any particular reason to use Diffie-Hellman over RSA for key exchange? Põhjalik Diffie-Hellmani ja RSA algoritmide võrdlus
• weakdh.org Veebileht Logjami rünnaku kohta